package club.babyf.nativeai.demo.algorithm;

import java.util.HashMap;
import java.util.Map;

/**
 * _30_LFUCache.
 *
 * @author zhanglei.
 * @date 2025/8/8 21:21.
 * @description LFU缓存.
 */
public class _30_LFUCache {

    public static class Node {

        int key;

        int value;

        int fre;

        Node prev;

        Node next;

        public Node(int key, int value, int fre) {
            this.key = key;
            this.value = value;
            this.fre = fre;
        }

    }

    public static class DLinkedNode {

        Node head;

        Node tail;

        public DLinkedNode() {
            head = new Node(0, 0, 0);
            tail = new Node(0, 0, 0);
            head.next = tail;
            tail.prev = head;
        }

        public void removeNode(Node node) {
            node.prev.next = node.next;
            node.next.prev = node.prev;
        }

        public void addToHead(Node node) {
            node.prev = head;
            node.next = head.next;
            head.next.prev = node;
            head.next = node;
        }

        public Node removeTail() {
            if (isEmpty()) {
                return null;
            }
            Node node = tail.prev;
            removeNode(node);
            return node;
        }

        public boolean isEmpty() {
            return head.next == tail;
        }

    }

    private final Map<Integer, Node> cacheMap;

    private final Map<Integer, DLinkedNode> freMap;

    private final int cacheCapacity;

    private int size;

    private int minFre;

    public _30_LFUCache(int cacheCapacity) {
        this.cacheMap = new HashMap<>();
        this.freMap = new HashMap<>();
        this.cacheCapacity = cacheCapacity;
        size = 0;
        minFre = 0;
    }

    public int get(int key) {
        if (cacheCapacity == 0 || !cacheMap.containsKey(key)) {
            return -1;
        }
        Node node = cacheMap.get(key);
        updateFre(node);
        return node.value;
    }

    public void put(int key, int value) {
        if (cacheCapacity == 0) {
            return;
        }
        if (cacheMap.containsKey(key)) {
            Node node = cacheMap.get(key);
            node.value = value;
            updateFre(node);
            return;
        }
        if (cacheCapacity == size) {
            DLinkedNode minList = freMap.get(minFre);
            Node minNode = minList.removeTail();
            if (minNode != null) {
                cacheMap.remove(minNode.key);
                size--;
            }
        }
        Node newNode = new Node(key, value, 1);
        cacheMap.put(key, newNode);
        freMap.computeIfAbsent(1, k -> new DLinkedNode()).addToHead(newNode);
        minFre = 1;
        size++;
    }

    private void updateFre(Node node) {
        int oldFre = node.fre;
        DLinkedNode oldList = freMap.get(oldFre);
        oldList.removeNode(node);

        if (oldList.isEmpty() && oldFre == minFre) {
            minFre++;
        }

        node.fre++;
        int newFre = node.fre;
        freMap.computeIfAbsent(newFre, k -> new DLinkedNode()).addToHead(node);
    }

}
